#include <iostream>  
#include <vector>  

using namespace std;

namespace test1 {
    // 快速排序的分区函数  
    int partition(vector<int>& arr, int low, int high) {
        int pivot = arr[high];    // 选择最后一个元素作为基准  
        int i = (low - 1);        // 较小元素的索引  

        for (int j = low; j <= high - 1; j++) {
            // 如果当前元素小于或等于pivot  
            if (arr[j] <= pivot) {
                i++;    // 移动较小元素的索引  
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[high]);
        return (i + 1);
    }

    // 快速排序函数  
    void quickSort(vector<int>& arr, int low, int high) {
        if (low < high) {
            // pi 是分区后基准的正确位置  
            int pi = partition(arr, low, high);

            // 分别对基准前后的子数组进行排序  
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    // 打印数组的函数  
    void printArray(const vector<int>& arr) {
        for (int i = 0; i < arr.size(); i++)
            cout << arr[i] << " ";
        cout << endl;
    }

    // 主函数来测试上述函数  
    int main4() {
        //vector<int> arr = { 2, 2, 1, 1, 1, 2, 2 };
        vector<int> arr = { 3, 2, 3 };
        int n = arr.size();

        quickSort(arr, 0, n - 1);

        cout << "Sorted array: \n";
        printArray(arr);
        // 1 1 1 2 2 2 2
        int majority = arr[0];
        int nowCount = 1;
        for (int i = arr.size() - 1; i > 0; i--)
        {
            if (arr[i] == majority)
            {
                nowCount++;
            }
            else
            {
                majority = arr[i];
                nowCount = 1;
            }
            if (nowCount >= arr.size() / 2) {
                cout << "majority:" << majority << endl;
                return 0;
            }
        }
        cout << "majority:" << majority << endl;
        return 0;
    }
}